program PROsad;

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  arrInt = array of integer;
var
  mass: array of arrInt;
  arr: array of integer;
  n, v, k, t, i1, i2, min, imin, sum: integer;
  fin: textfile;
  flag: boolean;

begin
  AssignFile (fin,'input.txt');
  Reset (fin);
  Readln (fin, n);
  Readln (fin, v);
  setlength (mass, n);
  for i1:=0 to n-1 do
    setlength (mass[i1], 5);
  for i1:= 0 to n-1 do
  begin
    read (fin, mass[i1][0]);
    read (fin, mass[i1][1]);
    readln (fin, mass[i1][2]);
    mass[i1][3]:=0;
    mass[i1][4]:=0;
  end;
  k:=v;
  t:=0;
  setlength (arr, n-1);
  for i1:= 1 to v-1 do
  begin
    for i2:= 0 to n-1 do
    begin
      if (mass[i2][1] = t) then
      begin
        mass[i2][3]:= mass[i2][3]+1;
        mass[i2][4]:=1;
      end;
      if (mass[i2][0] = t) then
      begin
        mass[i2][3]:= mass[i2][3]+1;
        mass[i2][4]:=0;
      end;
    end;
    flag:=false;
    for i2:=0 to n-1 do
    begin

      if (mass[i2][3]=1) and (flag=false) then
      begin
        flag:=true;
        imin:=i2;
        min:=mass[i2][2];
      end;
      if (mass[i2][3]=1) and (flag=true) then
      begin
        if (mass[i2][2]<min) then
        begin
          imin:=i2;
          min:=mass[i2][2];
        end;
      end;

    end;
    if (mass[imin][4]=0) then
    begin
      t:=mass[imin][1];
      arr[i1-1]:=imin;
    end;
    if (mass[imin][4]=1) then
    begin
      t:=mass[imin][0];
      arr[i1-1]:=imin;
    end;
  end;
  sum:=0;
  for i1:= 0 to n-2 do
  begin
    writeln (mass[arr[i1]][0], ' ', mass[arr[i1]][1]);
    sum:=sum+mass[arr[i1]][2];
  end;
  writeln ('minimal sum:', sum);
  Closefile (fin);
  readln;
end.
